package pers.qianyu.month_202103.date_20210306;

import java.util.*;

/**
 * 括号序列
 * https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117&tqId=37749&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
 *
 * @author mizzle rain
 * @date 2021-03-06 14:30
 */
public class IsValid {
    /**
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid(String s) {
        int n = s.length();
        if (n == 0) return true;
        if ((n & 1) == 1) return false;
        HashMap<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> st = new ArrayDeque<>();
        char[] arr = s.toCharArray();
        for (char c : arr) {
            if (!st.isEmpty() && st.getLast() == map.get(c)) {
                st.pollLast();
            } else {
                st.addLast(c);
            }
        }
        return st.isEmpty();
    }
}
